package com.lw.leetcode.dp.c;

import com.lw.test.util.Utils;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 1575. 统计所有可行路径
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/28 15:36
 */
public class CountRoutes {

    public static void main(String[] args) {
        CountRoutes test = new CountRoutes();
        // 4
//        int[] locations = {2, 3, 6, 8, 4};
//        int start = 1;
//        int finish = 3;
//        int fuel = 5;

        // 5
//        int[] locations = {4, 3, 1};
//        int start = 1;
//        int finish = 0;
//        int fuel = 6;

        // 0
//        int[] locations = {5, 2, 1};
//        int start = 0;
//        int finish = 2;
//        int fuel = 3;

        // 0
        int[] arr = Utils.getArr(120, 1, 200);
        int[] locations = Arrays.stream(arr).distinct().toArray();
        int start = 0;
        int finish = 2;
        int fuel = 200;
        System.out.println(Arrays.toString(locations));
        System.out.println(start);
        System.out.println(finish);
        System.out.println(fuel);

        int i = test.countRoutes(locations, start, finish, fuel);
        System.out.println(i);
    }

    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        long sum = 0;
        int n = locations.length;
        long[][] arr = new long[fuel + 1][n];
        for (int i = 0; i < n; i++) {
            int abs = Math.abs(locations[i] - locations[start]);
            if (abs <= fuel) {
                arr[abs][i] = 1;
            }
        }
        for (int i = 1; i <= fuel; i++) {
            long[] items = arr[i];
            for (int j = 0; j < n; j++) {
                long t = items[j] % 1000000007;
                if (t == 0) {
                    continue;
                }
                for (int k = 0; k < n; k++) {
                    if (k == j) {
                        continue;
                    }
                    int abs = Math.abs(locations[k] - locations[j]) + i;
                    if (abs <= fuel) {
                        arr[abs][k] += t;
                    }
                }
            }
        }
        for (long[] longs : arr) {
            sum = (sum + longs[finish]) % 1000000007;
        }
        return (int) sum;
    }

}
